The present invention is directed to methods and apparatus for providing an efficient Fast Fourier Transform (FFT) memory addressing and storage scheme, and more particularly to organizing and addressing data in the memory for use in computing an FFT.
The FFT is a fast (computationally efficient) way to calculate the Discrete Fourier Transform (DFT). Functionally, the FFT decomposes the set of data to be transformed into a series of smaller data sets to be transformed. Then, the FFT decomposes those smaller sets into even smaller sets. At each stage of processing, the results of the previous stage are combined in a special way. As defined herein, butterfly operations refer to the processing and combining of the subsets of the data. The “radix” of the FFT is defined as the size of an FFT data set decomposition.
An N-point (i.e., N data points), radix-r FFT, may be processed in logr(N) stages. At each stage of the FFT, (N/r) butterfly operations may be performed. For example, a 64-point radix-2 FFT may be processed in 6 stages where at each stage 32 butterfly operations are performed.
For each butterfly operation the number of simultaneous data points (i.e., a butterfly data set) that may be needed for processing may be equivalent to the radix of the FFT. Also, each butterfly operation may require a different butterfly data set, such that at the completion of the FFT stage, a number of combinations of butterfly data sets may be processed.
In order to provide a number of simultaneous data points for each FFT butterfly operation, the data may be arranged in several different memory data banks. In particular, each data bank may be used to store and provide one data point of the butterfly data set. For example, in a radix-4 FFT, four distinct data banks may be used, each providing one of the four data points needed for each FFT butterfly operation. This enables each data bank to receive a distinct address and provide the portion of the butterfly data set that is needed for the particular butterfly operation.
The butterfly data sets for each FFT stage may be addressed in accordance with a conventional bit reversal addressing scheme. The bit reversal addressing scheme may be used to compute the addresses for each data point in a butterfly data set at each FFT butterfly operation and stage.
Exemplary Table 1 below illustrates a conventional bit reversal addressing scheme for a 16-point, radix-2 FFT:
TABLE 11st (0, 8)(1, 9)(2, 10)(3, 11)(4, 12) (5, 13) (6,  (7, stage14)15)2nd (0, 4)(1, 5)(2, 6)(3, 7)(8, 12) (9, 13)(10, (11,stage14)15)3rd (0, 2)(1, 3)(4, 6)(5, 7)(8, 10) (9, 11)(12, (13, stage14)15)4th (0, 1)(2, 3)(4, 5)(6, 7)(8, 9)(10, 11)(12, (14, stage13)15)
Although the above FFT algorithm memory organization is useful, it lacks an efficient addressing scheme for reading butterfly data sets. In particular, for each butterfly data set, the number of different addresses that may be required to compute the butterfly operation may be equal to the radix of the FFT. For example, as illustrated in Table 1, at each FFT butterfly operation two distinct addresses may be computed. This limitation may increase cost and reduce efficiency in the FFT computation. This increases the complexity of address computation and data storage. Even if the data is arranged in a single multi-port memory module, the number of distinct addresses that may be needed for each FFT butterfly operation may increase linearly with the radix value of the FFT.
Additionally, even though address computation may seem insignificant for small radix FFT computations, the cost becomes prevalent for large data sets and high radix FFT computations. Also, such an addressing scheme requires a multi-bank or multi-port memory element which is often costly.
Accordingly, it is desirable to provide enhanced methods and apparatus for organizing, addressing and storing data in the memory for use in computing an FFT.